#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
const int maxn=10000;
const int INF=0x3f3f3f3f;
struct node {
    int y,w;
};
vector<node> p[maxn];
int dis[maxn];
bool vis[maxn];
int main()
{
    IOS;
    int n,e,w,a;
    char u,v,A;
    node temp;
    ifstream infile;
    //输入点数和边数
    cin>>n>>e;
    infile.open("a.txt");
    for(int i=0;i<e;i++){
        infile>>u>>v>>w;
        cout<<u<<" "<<v<<" "<<w<<endl;
        temp.y=v-'a'+1;temp.w=w;
        p[u-'a'+1].push_back(temp);
    }
    cin>>A;
    a=A-'a'+1;
    memset(dis,INF,sizeof(dis));
    memset(vis,false,sizeof(false));
    vis[a]=true;
    for(int i=0;i<p[a].size();i++){
        dis[p[a][i].y]=p[a][i].w;
    }
    dis[a]=0;
    //迪杰斯特拉求单源最短路
    for(int i=1;i<n;i++){
        int minn=INF,index;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&dis[j]<minn){
                minn=dis[j];
                index=j;
            }
        }
        vis[index]=true;
        for(int k=0;k<p[index].size();k++){
            int v=p[index][k].y;
            int w=p[index][k].w;
            if(!vis[v]&&dis[v]>dis[index]+w){
                dis[v]=dis[index]+w;
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<(char)(a+'a'-1)<<"->"<<(char)('a'+i-1)<<":"<<dis[i]<<endl;
    }
    getchar();
    getchar();
    return 0;
}
